package Hot100;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author zhangmin
 * @create 2021-12-31 10:25
 *
 * 岛屿系列问题--BFS/DFS
 * 200. 岛屿数量  ---计算所有岛屿的数量
 * 1254. 统计封闭岛屿的数目---去除边缘岛屿
 * 1020. 飞地的数量  ---不能到达边界的陆地数量，去除靠近边界的岛屿剩下的陆地面积
 * 695. 岛屿的最大面积 ----所有岛屿中面积最大值
 * 1905. 统计子岛屿  ----两个矩阵计算子岛屿
 * 694. 不同的岛屿数量（中等）
 *
 *
 */
public class numIslands200 {

    /**
     * 200. 岛屿数量
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 思路：BFS
     * 遍历每个节点，找到一个岛屿的点时，用BFS找出这个岛屿的所有位置，并将其淹没，全部变为0
     * */
    //从ij开始将与之相邻的陆地全部淹没,可以不用维护visited数组
    int[][] dir=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    void dfs(char[][] grid,int i,int j){
        int m=grid.length,n=grid[0].length;
        if (i<0||i>=m||j<0||j>=n){
            return;
        }
        if (grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';
        for (int[] d:dir) {
            int nexti=i+d[0];
            int nextj=j+d[1];
            dfs(grid,nexti,nextj);
        }
    }
    public int numIslands(char[][] grid) {
        int res=0;
        int m=grid.length,n=grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]=='1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }

    /**
     * 1254. 统计封闭岛屿的数目
     * 有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。
     * 如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。
     *
     * 思路：将200中的靠边的岛屿排除即可
     * */
    void dfs01(int[][] grid,int i,int j){
        int m=grid.length,n=grid[0].length;
        if (i<0||i>=m||j<0||j>=n){
            return;
        }
        if (grid[i][j]==1){
            return;
        }
        grid[i][j]=1;
        for (int[] d:dir) {
            int nexti=i+d[0];
            int nextj=j+d[1];
            dfs01(grid,nexti,nextj);
        }
    }
    public int closedIsland(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        for (int j = 0; j < n; j++) {
            //把靠上边的岛屿淹没掉
            dfs01(grid,0,j);
            //把靠下边的岛屿淹掉
            dfs01(grid,m-1,j);
        }
        for (int i = 0; i < m; i++) {
            dfs01(grid,i,0);
            dfs01(grid,i,n-1);
        }
        int res=0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]==0){
                    res++;
                    dfs01(grid,i,j);
                }
            }
        }
        return res;
    }



    /**
     * 1020. 飞地的数量
     * 给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。
     * 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。--封闭岛屿的面积
     * 思路：将靠边的陆地淹掉，然后去数剩下的陆地数量即可
     * */
    void dfs10(int[][] grid,int i,int j){
        int m=grid.length,n=grid[0].length;
        if (i<0||i>=m||j<0||j>=n){
            return;
        }
        if (grid[i][j]==0){
            return;
        }
        grid[i][j]=0;
        for (int[] d:dir) {
            int nexti=i+d[0];
            int nextj=j+d[1];
            dfs10(grid,nexti,nextj);
        }
    }
    public int numEnclaves(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        for (int i = 0; i < m; i++) {
            dfs10(grid,i,0);
            dfs10(grid,i,n-1);
        }
        for (int i = 0; i < n; i++) {
            dfs10(grid,0,i);
            dfs10(grid,m-1,i);
        }
        int res=0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]==1){
                    res+=1;
                }
            }
        }
        return res;
    }

    /**
     * 695. 岛屿的最大面积
     * 给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。
     * 你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
     * 思路：通过dfs找到每个岛屿的面积，计算最大的即可
     * */
    int dfs695(int[][] grid,int i,int j){
        int m=grid.length,n=grid[0].length;
        if (i<0||i>=m||j<0||j>=n){
            return 0;
        }
        if (grid[i][j]==0){
            return 0;
        }
        grid[i][j]=0;
        int res=1;
        for (int[] d:dir) {
            int nexti=i+d[0];
            int nextj=j+d[1];
            res+=dfs695(grid,nexti,nextj);
        }
        return res;
    }
    public int maxAreaOfIsland(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        int res=0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]==1){
                    int area = dfs695(grid, i, j);
                    res=Math.max(area,res);
                }
            }
        }
        return res;
    }

    /**
     * 1905. 统计子岛屿
     * 给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。
     * 一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
     * 如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，
     * 那么我们称 grid2 中的这个岛屿为 子岛屿 。请你返回 grid2 中 子岛屿 的 数目 。
     * 思路：每个位置判断，当B中的一片陆地在A中对应位置是海水，则B不是A的子岛
     * */
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int m=grid1.length,n=grid1[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid1[i][j]==0&&grid2[i][j]==1){
                    //这个岛屿不是子岛，淹掉
                    dfs10(grid2,i,j);
                }
            }
        }
        int res=0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid2[i][j]==1){
                    res++;
                    dfs10(grid2,i,j);
                }
            }
        }
        return res;
    }


    /**
     * 694.不同的岛屿数量
     * 输入一个二维矩阵，0 表示海水，1 表示陆地，这次让你计算 不同的 (distinct) 岛屿数量
     * 思路：对于形状相同的岛屿，如果从同一起点出发，dfs 函数遍历的顺序肯定是一样的
     * 用1,2,3,4分别表示方向为上下左右，用-1，-2，-3，-4分别表示为撤销上下左右
     * */
    void dfs694(int[][]grid,int i,int j,int d,StringBuffer path){
        int m=grid.length,n=grid[0].length;
        if (i<0||j<0||i>=m||j>=n||grid[i][j]==0){
            return;
        }
        grid[i][j]=0;
        path.append(d).append(',');
        for (int k = 0; k < dir.length; k++) {
            int[] next=dir[i];
            int nexti=i+next[0],nextj=j+next[1];
            dfs694(grid,nexti,nextj,i+1,path);
        }
        path.append(-d).append(",");
    }
    int numDistinctIslands(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        HashSet<String> islands=new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]==1){
                    StringBuffer path=new StringBuffer();
                    dfs694(grid,i,j,1,path);
                    islands.add(path.toString());
                }
            }
        }
        return islands.size();
    }

}
